\chapter{Metóda ProSSiGen}

V predošlej kapitole sme sa zbežne oboznámili s metódami porovnávajúce štruk\hyp túru bielkovín a získali sme tiež náčrt, ako využiť GP pri tomto procese porovnávania. Nakoniec sme si v analýze zhrnuli možnosti a smer, akým by sme sa mali k cieľu vybrať. V tejto časti si navrhneme objekty reprezentujúce jednotlivé časti celého priebehu zarovnávania a potom popíšeme celý proces programu ProSSiGen\footnote{ProSSiGen - skratka pre \textit{\textbf{P}rotein \textbf{S}tructure \textbf{Si}milarity Using \textbf{Gen}etic Programming}.}, ktorý je implementovaný v jazyku C++ s využitím knižníc Qt.

Jazyk C++ sme si vybrali kvôli jeho veľkej výhode a to rýchlosti, čo sa nám pri takejto algoritmicky náročnej úlohe hodí.

Qt knižnice v programe používame pre pohodlnejšie spracovanie konfigurač\hyp ného súboru vo formáte XML. Taktiež pre čítanie a zápis do súborov a pre implementáciu viacerých vlákien programu.

Aby sme sa pri návrhu objektov lepšie orientovali v úlohách jednotlivých objektov, načrtnime celý proces týmito bodmi:
\begin{itemize}
\item načítanie súboru, ktorý popisuje danú bielkovinu,
\item vytvorenie základných objektov,
\item vykonanie globálneho sekvenčného zarovnania,
\item prevod zarovnania na stromovú štruktúru,
\item algoritmy GP a výsledok.
\end{itemize}

\section{Návrh objektov}

Objekty používajúce v programe ProSSiGen implementujúce túto metódu môže\hyp me podľa využitia rozdeliť do troch skupín: na základné objekty, na objekty týkajúce sa globálneho zarovnania (dodatočné objekty) a na objekty reprezentujúce stromovú štruktúru v GP (\uv{stromové} objekty).

\subsection{Základné objekty}
\label{basic_objects}

Základné objekty vytvárame už počas načítavania informácií o bielkovine zo~súbo\hyp ru, ktorý celú bielkovinu popisuje. Poďme si ich zadefinovať a popísať ich úlohu.

\begin{description} 
\item[PdbAtom] \hfill \\
	Snáď najelementárnejší objekt, ktorý popisuje konkrétnu molekulu, jej názov a trojdimenzionálne súradnice. Ďalej obsahuje identifikátor (ID) a názov rezídua, ku ktorému sa viaže a tiež označenie bielkovinového reťazca\footnote{Anglicky: $chain$.}.

\item[PdbResidue] \hfill \\
	Objekt reprezentujúci rezíduum, ktorý obsahuje svoje ID, jedno-písmenkový názov aminokyseliny, ktorej je súčasťou a vektor (myslíme tým zoznam implementovaný ako \textit{std::vector}) ukazovateľov na atómy patriace tejto aminokyseline. Rezíduum vnímame v tomto objekte ako ukazovateľ na atóm, ktorý je rezíduum.
	
\item[ASphere] \hfill \\
	Okolo každého rezídua si predstavme sféru s nejakým polomerom a stredom, ktorý reprezentuje konkrétne rezíduum. Do tejto sféry ďalej zahrňme rezídua, ktorých všetky atómy (resp. celá aminokyselina) priestorovo patria do tejto sféry. Uvažujme len rezíduá, ktoré sa nachádzajú bezprostredne za, resp. pred stredom tejto sféry. Všetky rezíduá, ktoré predchádzajú stredom sféry a súčasne jej patria, nazveme \textit{upstream backbone} a všetky rezíduá, ktoré po strede sféry v reťazci nasledujú, nazveme \textit{downstream backbone}. 

	Samotný objekt obsahuje ukazovatele na rezíduá predstavujúce tieto čiastoč\hyp né reťazce, obsahuje ukazovateľ na rezíduum a tiež premennú vyjadrujúcu, či je sféra typu \textit{null}, kedy ASphere neobsahuje žiadne ukazovatele. Naša ASphere je okresanou verziou \textit{aa-sphere}, ktorú navrhol Galgonek a spol. v~metóde SProt~\cite{galgonek11}.
	
\item[SSE] \hfill \\
	Už z predošlej kapitoly vieme, že SSE znamená prvok (element), ktorý je sekundárnou štruktúrou. SSE implementujeme ako abstraktný objekt, ktorý obsahuje informáciu o type (\textit{SSEType}), ktorý má hodnotu buď \textit{Helix} --- myslíme ním SSE typu $\alpha$-helix, alebo \textit{Sheet} --- SSE typu $\beta$-skladaný list, alebo \textit{Loop} --- zvyšné časti reťazca, alebo \textit{NIL} --- podobne ako v metóde KENOBI~\cite{szustakowski00}, kde Szustakowski používal SSE typu \textit{null}. Naše SSE tiež obsahuje počiatočnú a terminačnú ASphere.
	
	Objekty SSE a informácie o nich sa načítavajú priamo zo súboru, t.j. nepoužívame žiadne ďalšie metódy na determináciu sekundárnych štruktúr. 
	
\item[PdbHelix] \hfill \\
	Objekt predstavujúci $\alpha$-helix, ktorý je odvodený (implementačne dedí) od objektu SSE. Je určený svojím seriálovým číslom, obsahuje ID rezídua, ktorým štruktúra začína a ID rezídua, ktorým daný $\alpha$-helix končí - to platí aj o ID reťazca.
	
\item[PdbSheet] \hfill \\
	Podobne ako PdbHelix, tak $\beta$-skladaný list obsahuje svoje seriálové číslo, počiatočné a koncové ID rezídua. Navyše obsahuje počet vlákien, z ktorých sa list skladá a údaj o smere medzi susednými vláknami - či je ten smer paralelný (rovnaký) alebo anti-paralelný (opačný).
	
\item[PdbLoop] \hfill \\
	Tento objekt obsahuje svoje ID a počiatočné, a koncové ID rezídua. Predstavuje časti štruktúry, ktoré nie sú ani $\alpha$-helixom ani $\beta$-skladaným listom.
	
\item[NilSSE] \hfill \\
	SSE typu \textit{NIL} je objekt typu SSE (abstraktný objekt) a neobsahuje žiadne rezídua.
	
\item[ProteinObj] \hfill \\
	Objekt obsahujúci zoznamy, ktoré uchovávajú ukazovatele na objekty typu PdbAtom, PdbResidue, PdbHelix, PdbSheet, PdbLoop a ASphere. Reprezentujeme ním teda celý proteín s konkrétnym kódom ID.

\end{description}

\subsection{Dodatočné objekty}

\begin{description}
\item[ProteinAlignedPair] (PAP) \hfill \\
	Tento objekt v sebe ukladá ukazovateľ na dva proteíny, ktoré sa najprv sekvenčne zarovnajú. Výsledkom toho je zoznam dvojíc ukazovateľov na objekty typu ASphere\footnote{Implementačne std::vector$<$std::pair$<$ASphere$^{*}$,ASphere$^{*}> >$.}. Tieto dvojice sú už zarovnané a spárované.

\item[TraceMatrixField] \hfill \\
	Pomocná štruktúra, ktorá predstavuje prvok matice, ktorý môže mať viac hodnôt typu \textit{TraceMatrixFieldEnum} (buď je hodnota \textit{Done}\footnote{Hodnota \textit{Done} sa priraďuje prvku na nulových súradniciach v matici, aby sme vedeli, kedy máme proces \textit{backtrack} ukončiť a vrátiť kompletné zarovnanie.}, alebo \textit{Left}, alebo \textit{Up}, alebo \textit{Diag}). Pri získavaní celého zarovnania (pri procese \textit{backtrack}) nám TraceMatrixField hovorí, ktorými smermi v matici sa môžeme vydať, aby sme získali kompletné zarovnanie.

\end{description}

\subsection{Stromové objekty}

Tieto objekty predstavujú jednotlivé uzly stromu. Spravidla každý objekt sa nachádza na konkrétnej úrovni, pričom strom má nemennú hĺbku.

\begin{description}

\item[APASphere] \hfill \\
	Objekt reprezentujúci list stromu, ktorý sa skladá z \textit{prvej} a \textit{druhej} a-sféry (objektu typu ASphere), t.j. sféry patriacej prvej (neklasifikovanej) a druhej (klasifikovanej) bielkovine. Implementačne sa jedná o ukazovatele na tieto a-sféry.

\item[APSSE] \hfill \\
	Uzol typu APSSE je objekt, ktorý obsahuje vektor vyššie opisovaných listov typu APASphere. Ďalej uchováva dva ukazovatele: na \textit{prvý} a \textit{druhý} objekt SSE. 
	
	Vzťah medzi APSSE a APASphere je taký, že \textit{prvá} sekundárna štruktúra je reprezentovaná všetkými prvými AP a-sférami (objekty typu APASphere) z vektoru, ktorý daný APSSE obsahuje. Nápodobne to platí s \textit{druhými} objektami. 
	
	Tento vzťah znázorňuje obrázok~\ref{fig:apashpere_apsse}, na ktorom máme jeden uzol typu APSSE, ktorý obsahuje dva objekty SSE - jeden patriaci bielkovine $A$, druhý patriaci bielkovine $B$. Ich index znamená, že sa jedná o prvé objekty typu SSE v bielkovine (sú na začiatku). Na APSSE sa môže napájať ľubovoľné množstvo AP a-sfér, my znázorňujeme prvé dve z celej sekvencie patriacej bielkovine $A$, resp. $B$.
	
\begin{figure}[h!]
\centering
\begin{tikzpicture}[level distance=3cm,
  level 1/.style={sibling distance=2.5cm},
  level 2/.style={sibling distance=7cm},
  level 3/.style={sibling distance=4cm}]
    \tikzstyle{every node}=[draw,scale=0.8]
    \node[circle,line width=2pt] { 
		\begin{tikzpicture}    
			\node[circle] {$\boldsymbol{APSSE}$}
		child { node[block, text width=1.5cm] {$SSE^{\mathlarger{A}}_\mathlarger{{1}}$} }
		child { node[block, text width=1.5cm] {$SSE^{\mathlarger{B}}_\mathlarger{{1}}$} }  ;
		\end{tikzpicture}
    }
       child { node[circle] { }
            child { node[circle,line width=2pt] {$\boldsymbol{APASphere_{1}}$} 
   				child { node {$ASphere^{A}_{1}$} } 
   				child { node {$ASphere^{B}_{1}$} } 			
            }
            child { node[circle,line width=2pt] {$\boldsymbol{APASphere_{2}}$}
				child { node {$ASphere^{A}_{2}$} } 
   				child { node {$ASphere^{B}_{2}$} } 
            }
        } 
    ;
\end{tikzpicture}
\caption{Vzťah medzi APASphere a APSSE}
\label{fig:apashpere_apsse}
\end{figure}

\item[APTree] \hfill \\
	Tento objekt predstavuje koreň celej stromovej štruktúry. Obsahuje vektor ukazovateľov na objekty typu APSSE. 

\begin{figure}[h!]
\centering
\begin{tikzpicture}[level distance=3.5cm,
  level 1/.style={sibling distance=7cm},
  level 2/.style={sibling distance=2cm},
  level 3/.style={sibling distance=7cm}]
    \tikzstyle{every node}=[draw,scale=0.8]
    \node[circle,line width=2pt] {\textbf{APTree}}
       child { node[circle] { 
			\begin{tikzpicture}    
			\node[circle] {$\boldsymbol{APSSE_{1}}$}
				child { node[block, text width=1.5cm] {$SSE^{\mathlarger{A}}_\mathlarger{{1}}$} }
				child { node[block, text width=1.5cm] {$SSE^{\mathlarger{B}}_\mathlarger{{1}}$} }  ;
			\end{tikzpicture}       
       }
       } 
              child { node[circle] { 
			\begin{tikzpicture}    
			\node[circle] {$\boldsymbol{APSSE_{2}}$}
				child { node[block, text width=1.5cm] {$SSE^{\mathlarger{A}}_\mathlarger{{2}}$} }
				child { node[block, text width=1.5cm] {$SSE^{\mathlarger{B}}_\mathlarger{{2}}$} }  ;
			\end{tikzpicture}       
       }
       }
    ;
\end{tikzpicture}
\caption{Vzťah medzi APTree a APSSE}
\label{fig:aptree_apsse}
\end{figure}

\end{description}

V našom prípade množina funkcií, v stromovej štruktúre predstavujú uzly, ktoré spájajú svojich potomkov (v strome), t.j. tieto uzly majú spájaciu funkciu a sú uzavreté v zmysle, že dovoľujú spájať len uzly s určitým typom (APTree môže spájať len uzly typu APSSE a APSSE môže spájať uzly typu APASphere).

\section{Proces}

Poďme si ďalej popísať priebeh prvých častí celej metódy, jej vstupy i dôležité algoritmy.

K programu je viazaný tiež konfiguračný súbor, v ktorom môžeme nastavovať rôzne parametre týkajúce sa samotného načítavania, globálneho sekvenčného zarovnávania a GP.

\subsection{Vstupy a inicializácia}

Program ProSSiGen sa spúšťa cez príkazový riadok, resp. v termináli a má tri vstupné parametre. Prvé dve sú ID porovnávajúcich sa bielkovín a tretí je názov adresára (relatívna cesta k nemu odkiaľ sa program spúšťa), kde sa nachádzajú PDB súbory s týmito bielkovinami. Tento proces sa vykonáva zavolaním metódy \textit{TestReadTwoProteinFiles} v triede \textit{Testing}.

Ku každému ID bielkoviny je potrebné ešte udať ID reťazca. Ako je formát PDB súbory definovaný, máme k dispozícii na stránkach \textit{Protein Data Bank}\footnote{http://www.wwpdb.org/documentation/format33/v3.3.html}. Príklad týchto parametrov môže vyzerať napr. takto: \uv{1c3v\_ 1kgsb pdb\_database\textbackslash}. To znamená, že načítavame bielkovinu s ID 1c3v a ak je piaty znak nie je písmeno, budeme načítavať prvý reťazec (\textit{a} reťazec); druhú bielkovinu s ID 1kgs a budeme porovnávať reťazec \textit{b} a popisujúce PDB súbory (s koncovkou \textit{.ent}) sa nachádzajú v adresári pdb\_database\textbackslash.

Po spracovaní parametrov nasleduje načítavanie a vytváranie základných objektov popisovaných v časti~\ref{basic_objects}, o čo sa stará trieda \textit{LoaderParser}.

Pre podrobnejší opis, ako sa program spúšťa, si odporúčame prezrieť užívateľ\hyp skú dokumentáciu v prílohe~\ref{app:user_documentation}.

\subsection{Globálne sekvenčné zarovnanie (GS)}

Po načítaní aplikujeme na bielkoviny algoritmus Needleman-Wunsch, ktorý je implementovaný funkciou \textit{AlignTwoProteins} triedy \textit{ProteinComparison}, ktorá vracia vektor ProteinAlignedPair objektov. Typicky ich býva niekoľko, keďže v \textit{backtrace} matici môže existovať viac ciest. Nad týmito vektormi dokončíme definíciu SSE objektov a všetkým a-sféram priradíme konkrétny SSE, ktorého sú súčasťou. 

Pripomeňme si funkciu $\psi\left(a_{i},b_{j}\right)$ vracajúcu hodnotu podobnosti aminokyselín $a_{i}$ a $b_{j}$. Pre každú dvojicu aminokyselín máme k dispozícii tabuľku BLOSUM62~\cite{henikoff92}, v~ktorej sa tieto hodnoty nachádzajú. Táto tabuľka sa odporúča pri ohodnocovaní používať spolu s $\Omega$ o hodnote $-4$. Ak nebude v konfiguračnom súbore zadaná, potom sa použije obyčajné ohodnocovanie, ktoré hovorí, že ak sa dve aminokyseliny zhodujú, ohodnotíme ho číslom $1$, inak je to $0$.

Existujú iné BLOSUM tabuľky a vyjadrujú predpokladanú evolučnú vzdialenosť porovnávaných proteínových sekvencií. Výsledok tohto zarovnania je vo~veľ\hyp kej miere závislý od týchto \uv{skórovacích} matíc.

\begin{figure}[h!]
\centering
\begin{tikzpicture}[scale=1, node distance = 0.4cm, auto,align=center]
    % Global alignment
    \node [text width=0.25cm,color=blue] (11) {\textbf{A}};
    \node [right of=11,text width=0.25cm] (21) {Q};
   	\node [right of=21,text width=0.25cm] (31) {S};
	\node [right of=31,text width=0.25cm,color=blue] (41) {\textbf{V}};
	
	\node [right of=41,text width=0.25cm,color=blue] (51) {\textbf{P}};
	\node [right of=51,text width=0.25cm] (61) {W};
	\node [right of=61,text width=0.25cm] (71) {G};
	\node [right of=71,text width=0.25cm] (81) {I};
	\node [right of=81,text width=0.25cm] (91) {S};
	\node [right of=91,text width=0.25cm] (101) {R};
	\node [right of=101,text width=0.25cm,color=blue] (111) {\textbf{V}};
	
	\node [right of=111,text width=0.25cm,color=blue] (121) {\textbf{Q}};
	\node [right of=121,text width=0.25cm] (131) {A};
	\node [right of=131,text width=0.25cm] (141) {P};
	\node [right of=141,text width=0.25cm] (151) {A};
	\node [right of=151,text width=0.25cm] (161) {A};
	\node [right of=161,text width=0.25cm] (171) {H};
	\node [right of=171,text width=0.25cm] (181) {N};
	\node [right of=181,text width=0.25cm,color=blue] (191) {\textbf{R}};
	
	\node [right of=191,text width=0.25cm,color=blue] (201) {\textbf{G}};
	\node [right of=201,text width=0.25cm] (211) {L};
	\node [right of=211,text width=0.25cm] (221) {T};
	\node [right of=221,text width=0.25cm] (231) {G};
	\node [right of=231,text width=0.25cm] (241) {S};
	\node [right of=241,text width=0.25cm] (251) {G};
	\node [right of=251,text width=0.25cm,color=blue] (261) {\textbf{V}};
	
	\node [right of=261,text width=0.25cm,color=blue] (271) {\textbf{K}};
	\node [right of=271,text width=0.25cm] (281) {V};
	\node [right of=281,text width=0.25cm] (291) {A};
	\node [right of=291,text width=0.25cm] (301) {V};		
	\node [right of=301,text width=0.25cm] (311) {L};
	\node [right of=311,text width=0.25cm,color=blue] (321) {\textbf{D}};
	
	%the second protein
    \node [below of=11,text width=0.25cm, node distance=1cm] (12) {-};
	\node [below of=21,text width=0.25cm, node distance=1cm] (22) {-};
	
	\node [below of=31,text width=0.25cm, node distance=1cm,color=blue] (32) {\textbf{N}};
	\node [below of=41,text width=0.25cm, node distance=1cm,color=blue] (42) {\textbf{V}};
	
	\node [below of=51,text width=0.25cm, node distance=1cm] (52) {-};
	\node [below of=61,text width=0.25cm, node distance=1cm] (62) {-};
	\node [below of=71,text width=0.25cm, node distance=1cm] (72) {-};
	\node [below of=81,text width=0.25cm, node distance=1cm] (82) {-};
	\node [below of=91,text width=0.25cm, node distance=1cm] (92) {-};
	
	\node [below of=101,text width=0.25cm, node distance=1cm,color=blue] (102) {\textbf{R}};
	\node [below of=111,text width=0.25cm, node distance=1cm] (112) {V};
	\node [below of=121,text width=0.25cm, node distance=1cm] (122) {L};
	\node [below of=131,text width=0.25cm, node distance=1cm] (132) {V};
	\node [below of=141,text width=0.25cm, node distance=1cm] (142) {-};
	\node [below of=151,text width=0.25cm, node distance=1cm,color=blue] (152) {\textbf{V}};
	
	\node [below of=161,text width=0.25cm, node distance=1cm,color=blue] (162) {\textbf{E}};
	\node [below of=171,text width=0.25cm, node distance=1cm,color=blue] (172) {\textbf{D}};
	
	\node [below of=181,text width=0.25cm, node distance=1cm,color=blue] (182) {\textbf{E}};
	\node [below of=191,text width=0.25cm, node distance=1cm] (192) {R};
	\node [below of=201,text width=0.25cm, node distance=1cm] (202) {D};
	\node [below of=211,text width=0.25cm, node distance=1cm] (212) {L};
	\node [below of=221,text width=0.25cm, node distance=1cm] (222) {-};
	\node [below of=231,text width=0.25cm, node distance=1cm] (232) {-};
	\node [below of=241,text width=0.25cm, node distance=1cm] (242) {-};
	\node [below of=251,text width=0.25cm, node distance=1cm] (252) {-};
	\node [below of=261,text width=0.25cm, node distance=1cm] (262) {-};
	\node [below of=271,text width=0.25cm, node distance=1cm] (272) {-};
	\node [below of=281,text width=0.25cm, node distance=1cm] (282) {-};
	\node [below of=291,text width=0.25cm, node distance=1cm] (292) {A};
	\node [below of=301,text width=0.25cm, node distance=1cm] (302) {-};
	\node [below of=311,text width=0.25cm, node distance=1cm] (312) {-};
	\node [below of=321,text width=0.25cm, node distance=1cm] (322) {D};

	\node [above of=11, node distance=0.15cm] (a11) {};
	\node [above of=41, node distance=0.15cm] (a41) {};
	\draw (a11.north) -- (a41.north);
	
	\coordinate (middle_a11_a41) at ($(a11)!0.5!(a41)$);		
	\node [above of=middle_a11_a41,transform shape,rotate=90, node distance=0.6cm] {\scriptsize{Loop}};
	
	\node [above of=51, node distance=0.15cm] (a51) {};
	\node [above of=111, node distance=0.15cm] (a111) {};
	\draw (a51.north) -- (a111.north);
	
	\coordinate (middle_a51_a111) at ($(a51)!0.5!(a111)$);		
	\node [above of=middle_a51_a111,transform shape,rotate=90, node distance=0.6cm] {\scriptsize{Helix}};
	
	\node [above of=121, node distance=0.15cm] (a121) {};
	\node [above of=191, node distance=0.15cm] (a191) {};
	\draw (a121.north) -- (a191.north);
	
	\coordinate (middle_a121_a191) at ($(a121)!0.5!(a191)$);		
	\node [above of=middle_a121_a191,transform shape,rotate=90, node distance=0.6cm] {\scriptsize{Helix}};
	
	\node [above of=201, node distance=0.15cm] (a201) {};
	\node [above of=261, node distance=0.15cm] (a261) {};
	\draw (a201.north) -- (a261.north);
	
	\coordinate (middle_a201_a261) at ($(a201)!0.5!(a261)$);		
	\node [above of=middle_a201_a261,transform shape,rotate=90, node distance=0.6cm] {\scriptsize{Loop}};

	\node [above of=271, node distance=0.15cm] (a271) {};
	\node [above of=321, node distance=0.15cm] (a321) {};
	\draw (a271.north) -- (a321.north);
	
	\coordinate (middle_a271_a321) at ($(a271)!0.5!(a321)$);		
	\node [above of=middle_a271_a321,transform shape,rotate=90, node distance=0.6cm] {\scriptsize{Loop}};

	\node [below of=12, node distance=0.15cm] (a12) {};
	\node [below of=22, node distance=0.15cm] (a22) {};
	\draw (a12.south) -- (a22.south);
	
	\coordinate (middle_a12_a22) at ($(a12)!0.5!(a22)$);		
	\node [below of=middle_a12_a22,transform shape,rotate=270, node distance=0.6cm] {\scriptsize{NIL}};

	\node [below of=32, node distance=0.15cm] (a32) {};
	\node [below of=42, node distance=0.15cm] (a42) {};
	\draw (a32.south) -- (a42.south);
	
	\coordinate (middle_a32_a42) at ($(a32)!0.5!(a42)$);		
	\node [below of=middle_a32_a42,transform shape,rotate=270, node distance=0.6cm] {\scriptsize{Loop}};

	\node [below of=52, node distance=0.15cm] (a52) {};
	\node [below of=92, node distance=0.15cm] (a92) {};
	\draw (a52.south) -- (a92.south);
	
	\coordinate (middle_a52_a92) at ($(a52)!0.5!(a92)$);		
	\node [below of=middle_a52_a92,transform shape,rotate=270, node distance=0.6cm] {\scriptsize{NIL}};

	\node [below of=102, node distance=0.15cm] (a102) {};
	\node [below of=152, node distance=0.15cm] (a152) {};
	\draw (a102.south) -- (a152.south);
	
	\coordinate (middle_a102_a152) at ($(a102)!0.5!(a152)$);		
	\node [below of=middle_a102_a152,transform shape,rotate=270, node distance=0.6cm] {\scriptsize{Sheet}};
	
	\node [below of=162, node distance=0.15cm] (a162) {};
	\node [below of=172, node distance=0.15cm] (a172) {};
	\draw (a162.south) -- (a172.south);
	
	\coordinate (middle_a162_a172) at ($(a162)!0.5!(a172)$);		
	\node [below of=middle_a162_a172,transform shape,rotate=270, node distance=0.6cm] {\scriptsize{Loop}};
	
	\node [below of=182, node distance=0.15cm] (a182) {};
	\node [below of=322, node distance=0.15cm] (a322) {};
	\draw (a182.south) -- (a322.south);
	
	\coordinate (middle_a182_a322) at ($(a182)!0.5!(a322)$);		
	\node [below of=middle_a182_a322,transform shape,rotate=270, node distance=0.6cm] {\scriptsize{Helix}};

%	\coordinate (1st) at ($(11)!0.5!(12)$);
%	\node (1stn) at (1st) {\scriptsize{1.}};
%	
%	\coordinate (4th) at ($(41)!0.5!(42)$);
%	\node (4thn) at (4th) {\scriptsize{4.}};
%	
%	\coordinate (5th) at ($(51)!0.5!(52)$);
%	\node (5thn) at (5th) {\scriptsize{5.}};
%	
%	\coordinate (10th) at ($(101)!0.5!(102)$);
%	\node (10thn) at (10th) {\scriptsize{10.}};
%	
%	\coordinate (11th) at ($(111)!0.5!(112)$);
%	\node (11thn) at (11th) {\scriptsize{11.}};
%	
%	\coordinate (12th) at ($(121)!0.5!(122)$);
%	\node (12thn) at (12th) {\scriptsize{12.}};
%	
%	\coordinate (24th) at ($(241)!0.5!(242)$);
%	\node (24thn) at (24th) {\scriptsize{24.}};
%	
%	\coordinate (28th) at ($(281)!0.5!(282)$);
%	\node (28thn) at (28th) {\scriptsize{28.}};
%	
%	\coordinate (32th) at ($(321)!0.5!(322)$);
%	\node (32thn) at (32th) {\scriptsize{32.}};	
	
	%\node [left of=MiddleG, node distance = 3cm] (lb_global) {\textbf{Globálne zarovnanie}};

	%\draw (11) -- (12);	
	%\draw (61) -- (62);
	%\draw (91) -- (92);
	%\draw (101) -- (102);
	%\draw (111) -- (112);
	%\draw (151) -- (152);
	%\draw (181) -- (182);
	
\end{tikzpicture}
\caption{Ilustrácia objektu ProteinAlignedPair s vyznačenými typmi SSE}
\label{fig:pap_sse}
\end{figure}

Ako môžeme vidieť na obrázku~\ref{fig:pap_sse}, všetky SSE okrem typu \textit{NIL} majú svoju počiatočnú a koncovú a-sféru, ktoré sú vždy ne-\textit{null}. A-sféry sú zobrazené jedno-písmenovým názvom aminokyseliny a v prípade  \textit{null} a-sféry je miesto písmena čiarka.

\subsection{Prevod PAP na APTree}

Po globálnom zarovnaní a vytvorení objektov PAP potrebujeme tieto objekty prekonvertovať na stromovú štruktúru, konkrétne na typ APTree. Vzhľadom na možnú veľkú dĺžku bielkovinového reťazca bola snaha o zložitosť prevodu rovnajúcej sa $O(n)$, kde $n$ je dĺžka zarovnania PAP.

V algoritme postupne prechádzame dvojice a-sfér v zarovnaní PAP, pričom zohľadňujeme faktory ako: či niektorá a-sféra v zarovnaní je začiatkom alebo koncom SSE; či sa konkrétna a-sféra patriaca niektorej bielkovine nachádza v~strede SSE (nie je koncom ani začiatkom).

\begin{figure}[h!]
\centering
\begin{tikzpicture}[level distance=1.25cm,
  level 1/.style={sibling distance=7cm},
  level 2/.style={sibling distance=1.7cm},
  level 3/.style={sibling distance=0.8cm}]
    \tikzstyle{every node}=[draw]
    \node[circle] (1st_tree) {}
        child { node {\scriptsize{Loop|NIL}}
			child { node[circle] {} 
	  			child { node[circle,color=blue] {A} }
	  			child { node[circle] {-} }
			}
			child { node[circle] {} 
	  			child { node[circle] {Q} }
	  			child { node[circle] {-} }
			}
        } 
        child { node {\scriptsize{Loop|Loop}}
            child { node[circle] {} 
	  			child { node[circle,color=blue] {S} }
	  			child { node[circle] {N} }
			}
			child { node[circle] {} 
	  			child { node[circle,color=blue] {V} }
	  			child { node[circle,color=blue] {V} }
			}
        }
    ;
	\node[circle,below of=1st_tree,node distance=5cm] (2nd_tree) {}
        child { node {\scriptsize{Helix|NIL}}
			child { node[circle] {} 
	  			child { node[circle,color=blue] {P} }
	  			child { node[circle] {-} }
			}
			child { node[circle] {} 
	  			child { node[circle] {W} }
	  			child { node[circle] {-} }
			}
			child { node[circle] {} 
	  			child { node[circle] {G} }
	  			child { node[circle] {-} }
			}
			child { node[circle] {} 
	  			child { node[circle] {I} }
	  			child { node[circle] {-} }
			}
			child { node[circle] {} 
	  			child { node[circle] {S} }
	  			child { node[circle] {-} }
			}
			child { node[circle] {} 
	  			child { node[circle] {R} }
	  			child { node[circle] {-} }
			}
			child { node[circle] {} 
	  			child { node[circle,color=blue] {V} }
	  			child { node[circle] {-} }
			}
        } 
    ; 
	\node[circle,right of=2nd_tree,node distance=6cm] (aptree) {APTree};
    \node[circle,below of=2nd_tree,node distance=5cm] (3rd_tree) {}
        child { node {\scriptsize{NIL|Sheet}}
			child { node[circle] {} 
	  			child { node[circle] {-} }
	  			child { node[circle,color=blue] {R} }
			}			
			child { node[circle] {} 
	  			child { node[circle] {-} }
	  			child { node[circle] {V} }
			}            
            child { node[circle] {} 
	  			child { node[circle] {-} }
	  			child { node[circle] {L} }
			}
			child { node[circle] {} 
	  			child { node[circle] {-} }
	  			child { node[circle] {V} }
			}
			child { node[circle] {} 
	  			child { node[circle] {-} }
	  			child { node[circle,color=blue] {V} }
			}
        }
        child { node {\scriptsize{NIL|Loop}}
			child { node[circle] {} 
	  			child { node[circle] {-} }
	  			child { node[circle,color=blue] {E} }
			}
			child { node[circle] {} 
	  			child { node[circle] {-} }
	  			child { node[circle,color=blue] {D} }
			}
        }        
    ; 
    \path [line] (1st_tree) -| (aptree);
    \path [line] (2nd_tree) -- (aptree);
    \path [line] (3rd_tree) -| (aptree);
\end{tikzpicture}
\caption{Časť výsledného prevodu zo zarovnania}
\label{fig:res_conver}
\end{figure}

Prevodom sa snažíme zoskupovať SSE rovnakého typu do jedného objektu APSSE. Načrtnime si podstatu prevodu opísaním obrázka~\ref{fig:res_conver}, ktorý je výsledkom prevodu niekoľkých prvých dvojíc a-sfér, resp. niekoľkých prvých AP a-sfér. Prvý objekt APSSE obsahuje v sebe SSE typu \textit{Loop} z prvej bielkoviny a SSE typu \textit{NIL} z druhej bielkoviny. A-sféry $A$ a $Q$ z prvej bielkoviny patria SSE typu \textit{Loop}, \textit{null} a-sféry patria druhému SSE typu \textit{NIL} (SSE typu \textit{NIL} môžu patriť len \textit{null} a-sféry).

Nasledujúce dve spárované dvojice a-sfér patria rovnakému typu SSE - typu \textit{Loop}. Vytvoríme teda APSSE obsahujúce dva SSE typu \textit{Loop} a do dvoch AP a-sfér vložíme príslušné a-sféry.

Ďalej nasledujú SSE typu \textit{Helix} a \textit{NIL}, celú prvú SSE zlúčime s celou SSE typu \textit{NIL}, pričom k druhej \textit{NIL} SSE pridáme ďalšie dve \textit{null} a-sféry, ktoré dodatočne vytvoríme. Keby sme na mieste druhých a-sfér v posledných dvoch dvojiciach tejto \textit{Helix} SSE mali a-sféry patriace typu \textit{Helix} (miesto typu \textit{Sheet}), vznikol by nový APSSE objekt, kam by sa priradili tieto posledné dve dvojice a-sfér.

Popíšme si komplexne, ako algoritmus funguje. Na vstupe je vektor AP a-sfér, čo sú dvojice a-sfér predstavujúce celý objekt PAP. Pre prechod používame jeden hlavný iterátor, ktorý ukazuje na tieto dvojice. Pri prechádzaní dvojíc, sa zaoberáme hlavne tým, či a-sféry, na ktoré iterátor práve ukazuje, predstavujú začiatok nejakého SSE. Špeciálne rozoberáme prípady, či sa jedná o SSE rovnakého alebo rozdielneho typu, alebo sa jedná o SSE typu \textit{NIL}. Ďalej všetky SSE okrem SSE typu \textit{NIL} môžu byť \textit{spárované} už s nejakou SSE rovnakého typu, čo znamená, že sme do stromu vložili APSSE s týmito SSE. Ak narazíme na dvojicu a-sfér reprezentujúce SSE rovnakého typu a ak jedno z SSE je už \textit{sprárované}, potom tieto SSE nebudeme vkladať do jedného APSSE, ale pre už spárované SSE vytvoríme SSE typu \textit{NIL}.

Nech $SSE_{X}$ znamená SSE typu $X$ a $SSE_{\mathlarger{\ast}}$ znamená SSE ľubovoľného typu SSE okrem \textit{NIL}. Popíšme si jednotlivé prípady, na ktoré druhy SSE reprezentované dvojicou a-sfér môžeme natrafiť (vždy na prvom mieste bude a-sféra z prvej bielkoviny):
\begin{description}
\item[začiatok $\boldsymbol{SSE_{X}}$ vs. začiatok $\boldsymbol{SSE_{X}}$] \hfill \\
	V tomto prípade vytvoríme novú APSSE s SSE o typu $X$ a vložíme všetky dvojice a-sfér, až kým aspoň jedna z nich neukončí dané SSE. Ak prejdeme jedno SSE celé a druhé nie, to druhé označíme ako \textit{spárované}.
	
\item[začiatok $\boldsymbol{SSE_{\mathlarger{\ast}}}$ vs. začiatok \textit{spárovaného} $\boldsymbol{SSE_{X}}$] \hfill \\
	Všeobecne v tomto prípade do nového APSSE objektu priradíme ako prvé SSE o typu \textit{NIL} a druhé bude $SSE_{X}$.  $SSE_{\mathlarger{\ast}}$ vkladáme do zásobníku, pre prípad, že $SSE_{\mathlarger{\ast}}$ sa neskôr spáruje s nasledujúcim SSE z druhej bielkoviny.
	
\item[začiatok \textit{spárovaného} $\boldsymbol{SSE_{X}}$ vs. začiatok $\boldsymbol{SSE_{\mathlarger{\ast}}}$] \hfill \\
	Analogicky ako v predchádzajúcom prípade.

\item[$\boldsymbol{SSE_{NIL}}$ vs. pokračovanie \textit{spárovaného} $\boldsymbol{SSE_{\mathlarger{\ast}}}$] \hfill \\
	V tomto prípade iterujeme ďalej, pričom dvojice a-sfér si ukladáme do zásobníka. Nakoniec môžeme natrafiť na jedno z troch nasledujúcich situácií:
	\begin{description}
	\item[začiatok $\boldsymbol{SSE_{\mathlarger{\ast}}}$ vs. pokračovanie \textit{spárovaného} $\boldsymbol{SSE_{\mathlarger{\ast}}}$] \hfill \\
		Vyprázdnime zásobník plný APSSE, ktoré vložíme do stromu a potom vložíme nové APSSE s SSE o type \textit{NIL} a $X$.
		
	\item[$\boldsymbol{SSE_{NIL}}$ vs. koniec \textit{spárovaného} $\boldsymbol{SSE_{\mathlarger{\ast}}}$] \hfill \\
		Tu len vyprázdnime zásobník plný APSSE, ktoré vložíme do stromu.
		
	\item[začiatok $\boldsymbol{SSE_{\mathlarger{\ast}}}$ vs. koniec \textit{spárovaného} $\boldsymbol{SSE_{X}}$] \hfill \\
		Prakticky rovnaký prípad ako prvý.
	\end{description}

\item[pokračovanie \textit{spárovaného} $\boldsymbol{SSE_{\mathlarger{\ast}}}$ vs. $\boldsymbol{SSE_{NIL}}$] \hfill \\
	Obdobne ako predchádzajúci prípad.
	
\item[začiatok $\boldsymbol{SSE_{Y}}$ vs. začiatok $\boldsymbol{SSE_{X}}$] \hfill \\
	Vytvoríme si dve APSSE, v jednom sa budú nachádzať SSE o type $Y$ a $NIL$, v druhom SSE o type $NIL$ a $X$. Postupne do APSSE vložíme príslušné AP a-sféry. Ak bude jedna z SSE končiť, t.j. natrafíme na terminačnú a-sféru, APSSE s touto SSE vložíme do stromu. Ak skončia na jednom mieste obe SSE (natrafíme na miesto, kde sú obe a-sféry terminačné), najskôr do stromu vložíme APSSE s prvou SSE a potom druhú APSSE.

\item[začiatok $\boldsymbol{SSE_{X}}$ vs. pokračovanie $\boldsymbol{SSE_{X}}$] \hfill \\
	Vytvoríme APSSE, do ktorého vložíme oba ${SSE_{X}}$ a vložíme ho do stromu. Až doiterujeme na miesto nejakej terminačnej a-sféry, potom druhé ${SSE_{X}}$ označíme ako \textit{spárované}.
	
\item[pokračovanie $\boldsymbol{SSE_{X}}$ vs. začiatok $\boldsymbol{SSE_{X}}$] \hfill \\
	Podobne ako v predošlom prípade.
	
\item[$\boldsymbol{SSE_{NIL}}$ vs. pokračovanie $\boldsymbol{SSE_{\mathlarger{\ast}}}$] \hfill \\
	V tomto prípade iterujeme a vkladáme do zásobníka AP a-sfér dvojice a-sfér odkazujúce sa na SSE typu \textit{NIL} a $SSE_{\mathlarger{\ast}}$ až dokiaľ nenarazíme na nejaký začiatok (SSE, ktoré by nasledovalo po SSE typu \textit{NIL}), resp. koniec $SSE_{\mathlarger{\ast}}$.

\item[pokračovanie $\boldsymbol{SSE_{\mathlarger{\ast}}}$ vs. $\boldsymbol{SSE_{NIL}}$] \hfill \\
	Analogicky podľa predošlého prípadu.

\item[začiatok $\boldsymbol{SSE_{Y}}$ vs. pokračovanie $\boldsymbol{SSE_{X}}$] \hfill \\	
	Vytvoríme APSSE o SSE typoch $Y$ a \textit{NIL} a vložíme do zásobníka APSSE. Ak natrafíme na koniec $SSE_{Y}$, vyprázdnime zásobník APSSE. Ak súčasne skončí aj $SSE_{X}$, najprv vložíme APSSE s $SSE_{X}$ a až potom vyprázdnime zásobník. V prípade, že $SSE_{Y}$ končiť nebude, do stromu vložíme len APSSE s $SSE_{X}$.

\item[pokračovanie $\boldsymbol{SSE_{X}}$ vs. začiatok $\boldsymbol{SSE_{Y}}$] \hfill \\
	Podobne ako v predchádzajúcom prípade.
	
\item[začiatok $\boldsymbol{SSE_{\mathlarger{\ast}}}$ vs. $\boldsymbol{SSE_{NIL}}$] \hfill \\
	V tomto prípade iterujeme a vkladáme do zásobníka AP a-sfér dvojice a-sfér odkazujúce sa na SSE typu $SSE_{\mathlarger{\ast}}$ a \textit{NIL} až pokým nenarazíme na nejaký začiatok (SSE, ktoré by nasledovalo po SSE typu \textit{NIL}), resp. koniec $SSE_{\mathlarger{\ast}}$. V prípade začiatku resp. konca pokračujeme ďalej v iterácii, inak v~prípade, kedy nastanú obe situácie, vyprázdnime všetky zásobníky, vložíme APSSE do stromu aj s novo vytvoreným APSSE obsahujúce AP a-sféry zo zásobníka.

\item[$\boldsymbol{SSE_{NIL}}$ vs. začiatok $\boldsymbol{SSE_{\mathlarger{\ast}}}$] \hfill \\
	Obdobne podľa predošlého opisu.

\end{description}

Tento celý algoritmus spúšťame v niekoľkých vláknach, podľa hodnoty v konfiguračnom súbore. Každé vlákno obstaráva a konvertuje jeden objekt PAP na APTree, ktorý si zoberie zo spoločného zásobníka, kde sú uložené objekty PAP.

\section{Genetické programovanie v ProSSiGen}

V tejto sekcii si opíšeme priebeh GP v programe. Implementačne sa o priebeh stará trieda \textit{GP}.  Algoritmus~\ref{alg:gp_prossigen} nižšie ilustruje princíp chodu GP v našej metóde.
{$ $}\\

\begin{algorithm}[H]
	\SetAlgoLined
	\caption{Proces GP pri porovnávaní}\label{alg:gp_prossigen}
		Nech $t = 0$ je počítadlo generácií\;
		Do prvotnej populácie $C(t)$ zaradíme všetky APTree objekty\;
		\While {$termina$\textit{čná}$~podmienka~neplat$\textit{í}}{
		Pre každého jedinca $x_{i}(t)$ spočítajme hodnotu \textit{fitness}\ $f(x_{i}(t))$;
		Zoraďme jedincov v populácii podľa \textit{fitness}\;
		Vytvorme nových potomkov, na ktorých bol aplikovaný operátor mutácie a vložme ich do novej populácie $C(t+1)$\;
		Vyberme novú populáciu $C(t+1)$\;
		Posuňme sa na ďalšiu generáciu, t.j. $t = t + 1$\;
		}
\end{algorithm}
{$ $}\\

Po tom, čo sme previedli všetky objekty PAP na objekty APTree, sme tiež získali jedincov v počiatočnej populácii. V prípade, že by týchto jedincov bolo málo (menej ako 10), je možné nechať niektorých rodičov \uv{prežiť} a presunúť do novej populácie. Tým by sme zvýšili počet jedincov v populácii, získali by sme tým viac štruktúrnych variácií. Avšak, zatiaľ nám postačia noví jedinci.

\subsection{\textit{Fitness} a selekčná funkcia}

Pre každú novú generáciu jedincov vrátane počiatočnej generácie musíme spočítať hodnotu \textit{fitness} všetkých indivíduí. Máme niekoľko možností, aké ohodnotenie použiť, no budeme používať funkciu RMSD\footnote{Root-Mean-Square Deviation.}:

\begin{equation} \label{eq:rmsd}
RMSD(x_{i}) = \sqrt{\frac{\sum_{j=1}^{M_{\mathlarger{x_{\mathlarger{i}}}}} \left(a_{j} - b_{j}\right)^{2}}{M_{\mathlarger{x_{i}}}}}
\end{equation}

Funkcia~\ref{eq:rmsd} $RMSD(x_{i})$ pre jedinca $x_{i}$ vráti jeho \textit{fitness} hodnotu. $M_{\mathlarger{x_{i}}}$ znamená počet spárovaných ne-\textit{null} a-sfér; $a_{j}$ je $j$-ta spárovaná ne-\textit{null} a-sféra prvej (neklasifikovanej) bielkoviny; podobne pre $b_{j}$.

Výpočet prebieha vo viacerých vláknach v zmysle, že jedno vlákno procesu počíta \textit{fitness} pre jedného jedinca a o výpočet RMSD sa stará metóda \textit{ComputeFitness} z triedy \textit{Scoring}.

Po spočítaní \textit{fitness} všetkých jedincov v populácii ich zoradíme podľa tejto hodnoty, aby sme v ďalšej časti mohli použiť selekčnú metódu \textit{Linear Rank Selection} opisovanú Thomasom B\"{a}ckom~\cite{back96}. 

Majme generáciu $C(t) = \lbrace x_{0}(t), x_{1}(t),\ldots,x_{\mu-1}(t)\rbrace$ s jedincami o počte $\mu$, ktorú sme zoradili od \uv{najlepšieho} jedinca po \uv{najhorší}, t.j. jedinec $x_{0}(t)$ v populácii $C(t)$ bude mať najlepšiu hodnotu \textit{fitness}. \textit{Linear Rank Selection} spočíva v tom, že jedincov pre kríženie alebo reprodukciu vyberáme na základe rebríčka a prednosť vo výbere dávame lepšie ohodnoteným jedincom. Výhoda je, že ak majú dvaja jedinci čo len minimálny rozdiel v ohodnotení, tento rozdiel sa prejaví rovnomerne medzi všetkými jedincami. Rovnako ak by v populácii existovali indivídua s veľmi dobrým ohodnotením, pri iných selekčných metódach by mali tieto indivídua veľmi veľkú prevahu v populácii, ale náš typ selekcie tento efekt eliminuje. 

Whitley \cite{whitley89} predstavil vo svojej práci vzorec~\ref{eq:rank}, pomocou ktorého priamym výpočtom získame index jedinca za požitia tejto selekčnej metódy.

\begin{equation} \label{eq:rank}
i =  \Bigg\lfloor \frac{\mu}{2(c-1)} \left( c - \sqrt{c^{2} - 4(c-1)\chi} \right) \Bigg\rfloor
\end{equation}

 V ňom Whitley používa dve premenné: $c$, čo je \textit{selective pressure} parameter, pre ktorý musí platiť $1< c \leq 2$ a čím je hodnota bližšia k $2$, tým budeme častejšie vyberať \uv{lepších} jedincov; $\chi$ je reálne náhodné číslo, pričom $\chi \in\left[0;1\right]$. Typicky má $c$ hodnotu $1.8$. Táto metóda je implementovaná funkciou \textit{PerformLinearRankSelection} triedy \textit{GPsUtility}.

\subsection{Kríženie objektov APTree}

Ohodnotenú a zoradenú populáciu rozdelíme na sub-populácie, ktorých počet závisí od počtu vlákien. V bode, kedy sa máme rozhodnúť, či budeme reprodukovať, alebo krížiť, za nás rozhodne parameter $p_{r}$ a $p_{c}$ konfigurovateľný v konfiguračnom súbore. Ak sa rozhodne, že budeme reprodukovať, pomocou selekčnej metódy vyberieme jedinca, ktorého zreprodukujeme do novej populácie. 

V prípade kríženia vyberieme pomocou \textit{Linear Rank Selection} dvoch jedincov, na ktorých zavoláme funkciu \textit{PerformCrossover}, ktorá vratí dvoch potomkov. Pri krížení je dôležité vybrať správny náhodný bod v štruktúre oboch rodičov. Rodičia, ktorí sú reprezentovaný objektom APTree, obsahujú dve \textit{mapy}\footnote{Implementačne std::map$<$int,int$>$.} s názvom \textit{FirstPairingResiduesIDs} a \textit{SecondPairingResiduesIDs}. Prvá \textit{mapa} má ako kľúče identifikačné čísla rezíduí prvej bielkoviny, ktorých hodnota je ID rezídua druhej bielkoviny, ktoré je s ním v APTree spárované. Obdobne to platí aj pre druhú \textit{mapu}.

Pri výbere náhodného bodu kríženia, si určíme kľúč $k_{1}$ na náhodnej pozícii $i$ v \textit{mape} prvého rodiča s hodnotou $h_{1}$. Následne sa pozrieme, či v \textit{mape} druhého rodiča na pozícii $i$ existuje kľúč $k_{2}$ a zistíme si hodnotu, na ktorú ukazuje --- označme ju $h_{2}$. Ak sa obe hodnoty $h_{1}$ a $h_{2}$ rovnajú, bod kríženia nám vyhovuje. Mohlo by sa tiež totiž stať, že rezíduum s ID $k_{2}$ by bolo spárované len s \textit{null} a-sférami, ktorých ID sa do týchto \textit{máp} nezaznamenávajú. 

\begin{figure}[h!]
\centering
\begin{tikzpicture}[level distance=1cm,
  level 1/.style={sibling distance=7cm},
  level 2/.style={sibling distance=2.5cm},
  level 3/.style={sibling distance=1.25cm}]
    \tikzstyle{every node}=[draw]
    \node[node distance=5cm] (1st_tree) {APTree}
        child { node {\scriptsize{APSSE}}
			child { node[circle] {} 
	  			child { node[circle] {$1^{A}_{ID}$} }
	  			child { node[circle] {null} }
			}			
			child { node[circle] {} 
	  			child { node[circle] {$2^{A}_{ID}$} }
	  			child { node[circle] {$1^{B}_{ID}$} }
			}            
            child { node[circle] {} 
	  			child { node[circle,line width=2pt] {$3^{A}_{ID}$} }
	  			child { node[circle,line width=2pt,color=blue] {$2^{B}_{ID}$} }
			}
			child { node[circle] {} 
	  			child { node[circle] {null} }
	  			child { node[circle] {$3^{B}_{ID}$} }
			}
        }       
    ;
    \node[draw=none,left of=1st_tree, node distance=3cm] {\textbf{Prvý rodič}};
    
    \node[below of=1st_tree,node distance=5cm,fill=black!5] (2nd_tree) {APTree}
        child { node[fill=black!5] {\scriptsize{APSSE}}
			child { node[circle,fill=black!5] {} 
	  			child { node[circle,fill=black!5] {$1^{A}_{ID}$} }
	  			child { node[circle,fill=black!5] {$1^{B}_{ID}$} }
			}			
			child { node[circle,fill=black!5] {} 
	  			child { node[circle,fill=black!5] {$2^{A}_{ID}$} }
	  			child { node[circle,fill=black!5] {null} }
			}            
            child { node[circle,fill=black!5] {} 
	  			child { node[circle,line width=2pt,fill=black!5] {$3^{A}_{ID}$} }
	  			child { node[circle,line width=2pt,color=blue,fill=black!5] {$2^{B}_{ID}$} }
			}
			child { node[circle,fill=black!5] {} 
	  			child { node[circle,fill=black!5] {$4^{A}_{ID}$} }
	  			child { node[circle,fill=black!5] {$3^{B}_{ID}$} }
			}
        }       
    ;
    \node[draw=none,left of=2nd_tree, node distance=3cm] {\textbf{Druhý rodič}};
\end{tikzpicture}
\caption{APTree objekty ako rodičia s bodom kríženia}
\label{fig:crossover_prossigen_parents}
\end{figure}

\begin{figure}[h!]
\centering
\begin{tikzpicture}[level distance=1cm,
  level 1/.style={sibling distance=5cm},
  level 2/.style={sibling distance=2.5cm},
  level 3/.style={sibling distance=1.25cm}]
     \tikzstyle{every node}=[draw]
    \node[node distance=5cm] (1st_tree) {APTree}
        child { node {\scriptsize{APSSE}}
			child { node[circle] {} 
	  			child { node[circle,fill=black!5] {$1^{A}_{ID}$} }
	  			child { node[circle,fill=black!5] {$1^{B}_{ID}$} }
			}			
			child { node[circle] {} 
	  			child { node[circle,fill=black!5] {$2^{A}_{ID}$} }
	  			child { node[circle,fill=black!5] {null} }
			} 
		} 
		child { node {\scriptsize{APSSE}}
            child { node[circle] {} 
	  			child { node[circle] {$3^{A}_{ID}$} }
	  			child { node[circle] {$2^{B}_{ID}$} }
			}
			child { node[circle] {} 
	  			child { node[circle] {null} }
	  			child { node[circle] {$3^{B}_{ID}$} }
			}
        }       
    ;
    \node[draw=none,left of=1st_tree, node distance=3cm] {\textbf{Prvý potomok}};
    
    \node[below of=1st_tree,node distance=5cm,fill=black!5] (2nd_tree) {APTree}
        child { node[fill=black!5] {\scriptsize{APSSE}}
			child { node[circle,fill=black!5] {} 
	  			child { node[circle] {$1^{A}_{ID}$} }
	  			child { node[circle] {null} }
			}			
			child { node[circle,fill=black!5] {} 
	  			child { node[circle] {$2^{A}_{ID}$} }
	  			child { node[circle] {$1^{B}_{ID}$} }
			}     
		}     
		child { node[fill=black!5] {\scriptsize{APSSE}}
            child { node[circle,fill=black!5] {} 
	  			child { node[circle,fill=black!5] {$3^{A}_{ID}$} }
	  			child { node[circle,fill=black!5] {$2^{B}_{ID}$} }
			}
			child { node[circle,fill=black!5] {} 
	  			child { node[circle,fill=black!5] {$4^{A}_{ID}$} }
	  			child { node[circle,fill=black!5] {$3^{B}_{ID}$} }
			}
        }       
    ;
    \node[draw=none,left of=2nd_tree, node distance=3cm] {\textbf{Druhý potomok}};
\end{tikzpicture}
\caption{APTree objekty ako potomkovia}
\label{fig:crossover_prossigen_children}
\end{figure}

Vo väčšine prípadov sa pri krížení hodnoty kľúčov (ID rezíduí) $k_{1}$ a $k_{2}$ rovnajú, čo je ideálny prípad. Ak sa hodnoty nerovnajú, vznikne v potomkoch náhodná mutácia, ktorej výsledok môže byť napr. duplikácia niektorej a-sféry za odstránenia inej a-sféry. Takáto náhodná mutácia je súčasťou princípu evolučných algoritmov.

Ako ďalší následok kríženia môže byť tiež rozdelenie jedného APSSE na dve APSSE objekty ako vidíme na obrázku~\ref{fig:crossover_prossigen_children}. To dáva väčšie možnosti pre mutačný proces v nasledujúcej sekcii.

\subsection{Mutácia nových jedincov}

Proces mutácie, ktorý aplikujeme na všetkých nových jedincov zaručuje zmenu usporiadania a párovania a-sfér. Na začiatku tohto procesu si v jedinci vyberieme dva susedné APSSE objekty z vektoru objektov APSSE, ktorý obsahuje koreň APTree stromu. Podľa toho, aké vlastnosti majú SSE v týchto susedných APSSE objektoch, vykonáme iné usporiadanie.
Budeme sa riadiť podľa týchto vzorov:
\begin{description}
\item[APSSE($\boldsymbol{SSE_{X}}$;$\boldsymbol{SSE_{X}}$) vs. APSSE($\boldsymbol{SSE_{X}}$;$\boldsymbol{SSE_{X}}$)] \hfill \\
	V tomto prípade, kedy dva susedné APSSE objekty obsahujú SSE rovnakých typov, si vyberieme posledný objekt AP a-sfér z prvého APSSE (z vektoru objektov APASphere), alebo prvý objekt AP a-sfér z druhého APSSE. Túto AP a-sféru rozdelíme na dve nové AP a-sféry a to tak, že prvú a-sféru spárujeme s novou \textit{null} a-sférou a podobne spárujeme druhú a-sféru s novou \textit{null} a-sférou. S nimi vytvoríme aj nové objekty APSSE, do ktorých ich zaradíme. Vzor výsledku by mal vyerať ako je ilustrované na obrázku~\ref{fig:first_pattern_mutation}.
	
	
\begin{figure}[h!]
\centering
\begin{tikzpicture}[level distance=1cm,
  level 1/.style={sibling distance=1.5cm},
  level 2/.style={sibling distance=1.5cm},
  level 3/.style={sibling distance=1.25cm}]
     \tikzstyle{every node}=[draw]
    \node[circle] (1st_tree) {}
        child { node[circle] {$1^{A}_{X}$} }
        child { node[circle] {$1^{B}_{X}$} }
    ;
    \node[right of=1st_tree,node distance=4cm] (2nd_tree) {\scriptsize{X|NIL}}
    	child { node[circle] {} 
        	child { node[circle] {$1^{A}_{X}$} }
        	child { node[circle] {null} }
        }
    ;
    \node[right of=2nd_tree,node distance=3cm] (3rd_tree) {\scriptsize{NIL|X}}
    	child { node[circle] {} 
        	child { node[circle] {null} }
        	child { node[circle] {$1^{B}_{X}$} }
        }
    ;
\end{tikzpicture}
\caption{Vznik nových AP a-sfér a objektov APSSE}
\label{fig:first_pattern_mutation}
\end{figure}
	
\item[APSSE($\boldsymbol{SSE_{X}}$;$\boldsymbol{SSE_{X}}$) vs. APSSE($\boldsymbol{SSE_{X}}$;$\boldsymbol{SSE_{NIL}}$)] \hfill \\
	Keď tri SSE objekty sú rovnakého typu a jeden SSE je typu \textit{NIL}, vyberáme poslednú AP a-sféru z prvého objektu APSSE (keby boli objekty APSSE vo~vzore v opačnom poradí, vybrali by sme prvú AP a-sféru z druhého APSSE objektu). Túto AP a-sféru tiež rozdelíme na dve nové AP a-sféry a jednu z nich (tú, ktorá korešponduje s poradím typov SSE objektov) vložíme do druhého APSSE objektu (resp. do vektoru AP a-sfér), kde je jeden SSE objekt typu \textit{NIL}.
	
	Obdobné postupy aplikujeme aj pri ostatných permutáciách (ďalších troch), kde jeden SSE objekt je typu \textit{NIL}.
	
\item[APSSE($\boldsymbol{SSE_{X}}$;$\boldsymbol{SSE_{NIL}}$) vs. APSSE($\boldsymbol{SSE_{NIL}}$;$\boldsymbol{SSE_{X}}$)] \hfill \\
	Ak proti sebe máme postavené APSSE objekty s SSE objektami o typoch $X$ a \textit{NIL} vs. \textit{NIL} a $X$, vyberieme poslednú AP a-sféru z prvého APSSE a prvú AP a-sféru z druhého APSSE, a spojíme ich dokopy s vytvorením nového objektu APSSE s SSE o typoch $X$ a $X$.
	
\item[APSSE($\boldsymbol{SSE_{NIL}}$;$\boldsymbol{SSE_{X}}$) vs. APSSE($\boldsymbol{SSE_{X}}$;$\boldsymbol{SSE_{NIL}}$)] \hfill \\
	Tu postupujeme rovnako ako v predchádzajúcom prípade.
	
\end{description}

\subsection{Terminačné kritérium}

Evolučný proces sa zastaví na generácii $C(t)$ alebo ak sa v populácii nájde jedinec, ktorý spĺňa určitú hranicu ohodnotenia. Počet generácií aj hraničné ohodnotenie môžeme meniť v konfiguračnom súbore.